#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;

/*HJJ QQ479287006
 * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
 *输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
//[-2,  1,   -3,   4,  -1,   2,   1,   -5,  4]
// -2   1    -2    4    3    5    6     1   5
//  dp[i] = Math.max(dp[i-1] + nums[i],nums[i]);
1. 确定dp数组（dp table）以及下标的含义  dp[i] 当前下标对应的最大连续子数组的和
2. 确定递推公式    max(dp[i-1]+now,now)
3. dp数组如何初始化 开始为dp[0]=ar[0];
4. 确定遍历顺序  从头开始就行
5. 举例推导dp数组
 * */
int maxSubArray(vector<int> &nums) {

    vector<int> dp(nums.size());

    dp[0] = nums[0];
    int maxNum = nums[0];
    for (int i = 0; i < nums.size(); ++i) {
        dp[i] = max(dp[i - 1] + nums[i], nums[i]);
        maxNum = max(dp[i], maxNum);
    }

    return maxNum;

}